package sortAlgorithm;

import java.util.Arrays;

/**
 * 桶排序——记数排序
 * 适合知道元素范围、元素数量大的情况
 * 时间复杂度为O(n+k) 其中n是数组的长度， k是数组元素的范围值。
 * @author 胡宇轩
 * @Email: yuxuan.hu01@bianlifeng.com
 */
public class CountSort {
    // 本题假设数组中的元素范围为 0 - 9
    public static void main(String[] args) {
        int[] arr = new int[]{1,4,5,0,3,2,2,4,2,1,6,9,5};
        System.out.println(Arrays.toString(countSortStabled(arr)));
    }

    /**
     * 基本实现，但是不稳定
     * */
    static int[] countSort(int[] nums){
        int[] result = new int[nums.length];
        // 记数数组 0 ~ 9的元素范围
        int[] count = new int[10];
        for(int r : nums){
            count[r]++;
        }
        for (int i = 0,j = 0; i < count.length; i++) {
            while(count[i]-- >0){
                result[j++] = i;
            }
        }
        return result;
    }


    /**
     * 实现稳定的记数排序法
     * */
    static int[] countSortStabled(int[] nums){
        int[] result = new int[nums.length];
        // 记数数组 0 ~ 9的元素范围
        int[] count = new int[10];
        for(int r : nums){
            count[r]++;
        }
        for (int i = 1; i < count.length; i++) {
            count[i] = count[i] + count[i-1];
        }

        for (int i = nums.length-1; i >= 0 ; i--) {
            result[--count[nums[i]]] = nums[i];
        }
        return result;
    }

}
